package leetcodev1.链表;

public class LeetCode21 {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode virtualHead = new ListNode(-1),index = virtualHead;
        ListNode p = list1, q = list2;//这两个变量可以节约掉 并不重要
        while (p != null || q != null) {
            int num1 = p == null ? Integer.MAX_VALUE : p.val;
            int num2 = q == null ? Integer.MAX_VALUE : q.val;

            if (num1 <= num2) {
                index.next = p;
                p = p.next;
            } else {
                index.next = q;
                q = q.next;
            }

            index = index.next;
        }
        return virtualHead.next;
    }
}

class Answer21 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;//链表相比于数组的优势

        return prehead.next;
    }

    //递归版，也是一种思路吧..
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists1(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists1(l1, l2.next);
            return l2;
        }
    }
}
